package com.mxw.leetcode.D3回溯算法;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class H03无重复元素不可重复大小为K的组合 {

    /**
     * 返回数组中中所有可能的 k 个数的组合。
     * =》给你输入一个数组 nums = [1,2..,n] 和一个正整数 k，请你生成所有大小为 k 的子集。
     * =》只需要把第2层（根节点视为第 0 层）的节点收集起来，就是大小为2的所有组合：
     * {1,2,3}
     * [[1, 2], [1, 3], [2, 3]]
     */

    static List<List<Integer>> res = new LinkedList<>();
    // 记录回溯算法的递归路径
    static LinkedList<Integer> track = new LinkedList<>();

    static Integer number = 0;

    // 主函数
    static public List<List<Integer>> combine(int[] nums, int k) {
        number = k;
        backtrack(nums, 0);
        return res;
    }

    static void backtrack(int[] nums, int start) {
        // base case
        if (number == track.size()) {
            // 遍历到了第 k 层，收集当前节点的值
            res.add(new LinkedList<>(track));
            return;
        }
        // 回溯算法标准框架
        for (int i = start; i < nums.length; i++) {
            // 选择
            track.addLast(nums[i]);
            // 通过 start 参数控制树枝的遍历，避免产生重复的子集
            backtrack(nums, i + 1);
            // 撤销选择
            track.removeLast();
        }
    }


    public static void main(String[] args) {
        List<List<Integer>> subsets = combine(new int[]{1,2,3},3);
        System.out.println(Arrays.toString(subsets.toArray()));
    }
}
